/*
Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
*/

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        if (!s.length()) return res;
        vector<string> tmpres;
        restore_helper(0, s, tmpres, res);
        return res;
    }
private: 
    void restore_helper(int offset, string &s, vector<string> &tmpres, vector<string> &res) {
        if (tmpres.size() == 4) {
            string s("");
            for (int k = 0; k < 3; k++) {s.append(tmpres[k]); s.append(1, '.');}
            s.append(tmpres[3]); res.push_back(s);
            return;
        }
        int end = (s[offset] == '0')?1:3;
        for (int i = 1; i <= end; i++) {
            // check too long or too short 
            if ((offset+i-1 > s.length()-1 ) ||
                (offset+i + 3*(3-tmpres.size()) < s.length())) continue;
            string str = s.substr(offset, i);
            if (stoi(str) > 255) continue; // out of range
            tmpres.push_back(str);
            restore_helper(offset+i, s, tmpres, res);
            tmpres.pop_back();
        }
    }
};
